package cuiyt.leetcode.tree;

import cuiyt.leetcode.TreeNode;

import java.util.*;

/**
 * 二叉树前序遍历 使用迭代进行处理
 */
public class T144二叉树的前序遍历_迭代 {

    /**
     * 左 中 右 进行递归遍历
     * @param args
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        ArrayList<Integer> list = new ArrayList<>();
        printTreeByLeft(root, list);
        System.out.println(list);
    }

    public static void printTreeByLeft(TreeNode node,  ArrayList<Integer> list){
        if(Objects.isNull(node)){
            return;
        }
        // 使用队列 来模拟递归时候的栈
        // 按照前序遍历的方式 将元素逐个入栈，当前节点遍历完成之后，则将节点出栈，进行下一个元素的前序遍历
        Deque<TreeNode> stack = new LinkedList<>();
        /**
         * 结束标记，stack 为空
         */
        while (!stack.isEmpty() || node != null){
            // 当前节点的 左子树遍历， 左子树遍历完毕，结束
            while (node != null){
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            // 出栈，开始遍历 右子树
            node = stack.pop();
            node = node.right;
        }
    }

    public static void printTreeByLeftV2(TreeNode head,  ArrayList<Integer> list){
        if(Objects.isNull(head)){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 存放头节点
        stack.push(head);
        while (!stack.isEmpty()){
            // 从栈中获取节点，作为当前遍历二叉树的 根节点
            TreeNode node = stack.pop();
            list.add(node.val);
            // 左子树
            if(node.left !=null){
                stack.push(node.left);
            }
            // 右子树
            if(node.right !=null){
                stack.push(node.right);
            }
        }
    }
}
